package com.breeze.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/linked-list-cycle-ii/
 * 142. 环形链表 II
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * <p>
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
 * <p>
 * 说明：不允许修改给定的链表。
 * <p>
 * 进阶：
 * <p>
 * 你是否可以使用 O(1) 空间解决此题？
 */
public class LeetCode142 {

    // 方法一：哈希表，同LeetCode141，只不过返回的是节点
    public ListNode detectCycle(ListNode head) {
        // 存储的是每个节点的引用地址
        Set<ListNode> sets = new HashSet<>();
        while (head != null) {
            if (sets.contains(head)) {
                return head;
            }
            sets.add(head);
            head = head.next;
        }
        return null;
    }

    /**
     * 方法二：
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * 设链表共有 a+b 个节点，其中 链表头部到链表环入口 有 a 个节点（不计环入口节点）， 链表环有 b 个节点
     */
    public ListNode detectCycle1(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (true) {
            // 五环
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            // 相遇即存在环
            if (slow == fast) {
                break;
            }
        }
        // 得出环长b
        int b = 1;
        ListNode start = fast.next;
        while (start != fast) {
            b++;
            start = start.next;
        }
        // fast 先走 b步
        fast = head;
        for (int i = 0; i < b; i++) {
            fast = fast.next;
        }

        // 此时 fast 和head 同时行走，当 head 走 a 步时，fast 走了 b+a步，此时相遇节点即为环头。
        while (fast != head) {
            head = head.next;
            fast = fast.next;
        }
        return fast;
    }

    /**
     * 方法三：方法二的优化版
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     * 解：
     * 设链表共有 a+b 个节点，其中 链表头部到链表环入口 有 a 个节点（不计环入口节点）， 链表环有 b 个节点
     * 设f,s分别为fast和slow走过的距离,fast和slow相遇时，绕了环n圈
     * 由 f = s + nb; f = 2s 推到出 s = nb,如果fast从头开始走，slow依然从之前相遇处开始走，第一次相遇点就是 f = a, s = a+nb，节点就是环头
     */
    public ListNode detectCycle2(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            // 无环（只要fast指向了null，说明无环）
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            // 相遇即存在环
            if (fast == slow) {
                break;
            }
        }
        // fast 站在头节点，slow依然在nb的位置，两人起步走，相遇即为环头
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args) {
        LeetCode142 leetCode142 = new LeetCode142();
        ListNode head = new ListNode(3);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(0);
        ListNode forth = new ListNode(-4);
        head.next = second;
        second.next = third;
        third.next = forth;
        forth.next = second;
        System.out.println(leetCode142.detectCycle1(head) == second);
    }
}
